﻿//【进阶】36.模拟实现unordered_map&set
//【头文件包含】
//C++的主要头文件
#include<iostream>//c++的输入输出流
using namespace std;
#include<string>
#include<vector>
#include<list>
//C的主要头文件
//#include<stdio.h>
//#include<stdlib.h>
//#include<assert.h>
//#include<string.h> 
#include"HashTable.h"
#include"MyUnorderedMap.h"
#include"MyUnorderedSet.h"

//【命名空间】

//【类声明】

//【函数声明】
void Test1();void Test2();void Test3();


//【主函数】
int main()
{
	cout << "****主函数开始****" << endl;
	Test1();
	Test2();
	Test3();
	cout << "****主函数结束****" << endl;
	return 0;
}

//【函数定义】

/*测试用例*/void Test1()
{
	cout << "****测试用例开始****"<< endl;
	CLOSE_HASH::TestHashTable_Closed();
	cout << "****测试用例结束****" << endl << endl;
}

/*测试用例*/void Test2()
{
	cout << "****测试用例开始****" << endl;
	OPEN_HASH::TestHashTable_Open1();
	cout << "****测试用例结束****" << endl<<endl;
}

/*测试用例*/void Test3()
{
	cout << "****测试用例开始****" << endl;
	OPEN_HASH::TestHashTable_Open2();
	myspace::TestUnorderedSet1();
	myspace::TestUnorderedMap1();
	cout << "****测试用例结束****" << endl << endl;
}




//【笔记】
//【进阶】36.模拟实现unordered_map&set	
	//解决冲突的方法
		//1.闭散列--开放定制法(不推荐)（当前位置冲突，找空位置）(不能满了再增容，需要判断负载因子，负载因子和效率负相关)
		//2.开散列--拉链法（哈希桶）（冲突元素在统一映射下链接存储起来）
			//原理 
				// 以链表的形式将冲突的元素链接在对应映射位置下
				// 虽然开散列可以较好解决负载冲突，但随着冲突元素增多，效率也会降低
				// 因此开散列把负载因子控制到1，满负载也需要增容
			// 极端情况
				// 假设一条哈希桶链长度很长，超过一定长度会影响效率，可以将该位置的链式结构替换为红黑树结构
			// 迭代器“有序（插入顺序）”遍历 
				// 如果想在使用迭代器遍历哈希表时按插入顺序遍历，那么需要给哈希表增加两个成员变量作为当对象的前对象指针和后对象指针
				// 响应的在进行插入删除时需要额外处理这两个成员变量所代表的前后关系 

		









